{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Plates Between Candles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #binary-search #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #二分查找 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: platesBetweenCandles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #蜡烛之间的盘子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长桌子，桌子上盘子和蜡烛排成一列。给你一个下标从 <strong>0</strong>&nbsp;开始的字符串&nbsp;<code>s</code>&nbsp;，它只包含字符&nbsp;<code>'*'</code> 和&nbsp;<code>'|'</code>&nbsp;，其中&nbsp;<code>'*'</code>&nbsp;表示一个 <strong>盘子</strong>&nbsp;，<code>'|'</code>&nbsp;表示一支&nbsp;<strong>蜡烛</strong>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;表示 <strong>子字符串</strong>&nbsp;<code>s[left<sub>i</sub>...right<sub>i</sub>]</code>&nbsp;（<strong>包含左右端点的字符</strong>）。对于每个查询，你需要找到 <strong>子字符串中</strong>&nbsp;在 <strong>两支蜡烛之间</strong>&nbsp;的盘子的 <b>数目</b>&nbsp;。如果一个盘子在 <strong>子字符串中</strong>&nbsp;左边和右边 <strong>都</strong>&nbsp;至少有一支蜡烛，那么这个盘子满足在 <strong>两支蜡烛之间</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>s = \"||**||**|*\"</code>&nbsp;，查询&nbsp;<code>[3, 8]</code>&nbsp;，表示的是子字符串&nbsp;<code>\"*||<strong><em>**</em></strong>|\"</code>&nbsp;。子字符串中在两支蜡烛之间的盘子数目为&nbsp;<code>2</code>&nbsp;，子字符串中右边两个盘子在它们左边和右边 <strong>都 </strong>至少有一支蜡烛。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个整数数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"ex-1\" src=\"https://assets.leetcode.com/uploads/2021/10/04/ex-1.png\" style=\"width: 400px; height: 134px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"**|**|***|\", queries = [[2,5],[5,9]]\n",
    "<b>输出：</b>[2,3]\n",
    "<b>解释：</b>\n",
    "- queries[0] 有两个盘子在蜡烛之间。\n",
    "- queries[1] 有三个盘子在蜡烛之间。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"ex-2\" src=\"https://assets.leetcode.com/uploads/2021/10/04/ex-2.png\" style=\"width: 600px; height: 193px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"***|**|*****|**||**|*\", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]\n",
    "<b>输出：</b>[9,0,0,0,0]\n",
    "<strong>解释：</strong>\n",
    "- queries[0] 有 9 个盘子在蜡烛之间。\n",
    "- 另一个查询没有盘子在蜡烛之间。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含字符&nbsp;<code>'*'</code> 和&nbsp;<code>'|'</code>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt; s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [plates-between-candles](https://leetcode.cn/problems/plates-between-candles/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [plates-between-candles](https://leetcode.cn/problems/plates-between-candles/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"**|**|***|\"\\n[[2,5],[5,9]]', '\"***|**|*****|**||**|*\"\\n[[1,17],[4,5],[14,17],[5,11],[15,16]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "      stack = []\n",
    "      n = len(s)\n",
    "      for i in range(n):\n",
    "        if s[i] == \"|\": stack.append(i)\n",
    "      if len(stack) < 2:  return [0] * len(queries)\n",
    "\n",
    "      visited = dict()\n",
    "      def check(idx):\n",
    "        if idx in visited:\n",
    "          return visited[idx]\n",
    "        L, R = 0, len(stack) - 1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if idx > stack[mid]:  L = mid + 1\n",
    "          else: R = mid - 1\n",
    "        visited[idx] = L\n",
    "        return L\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        L = check(queries[i][0])\n",
    "        if L == len(stack): \n",
    "          queries[i] = 0\n",
    "          continue\n",
    "        R = check(queries[i][1])\n",
    "        if L == R:\n",
    "          queries[i] = 0\n",
    "          continue\n",
    "        if R == len(stack) or stack[R] > queries[i][1]:\n",
    "          R -= 1\n",
    "        queries[i] = stack[R] - stack[L] - R + L\n",
    "      return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "      stack = []\n",
    "      n = len(s)\n",
    "      for i in range(n):\n",
    "        if s[i] == \"|\": stack.append(i)\n",
    "      if len(stack) < 2:  return [0] * len(queries)\n",
    "\n",
    "      visited = dict()\n",
    "      def check(idx):\n",
    "        if idx in visited:\n",
    "          return visited[idx]\n",
    "        L, R = 0, len(stack) - 1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if idx > stack[mid]:  L = mid + 1\n",
    "          else: R = mid - 1\n",
    "        visited[idx] = L\n",
    "        return L\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        L = check(queries[i][0])\n",
    "        if L == len(stack): \n",
    "          queries[i] = 0\n",
    "          continue\n",
    "        R = check(queries[i][1])\n",
    "        if L == R:\n",
    "          queries[i] = 0\n",
    "          continue\n",
    "        if R == len(stack) or stack[R] > queries[i][1]:\n",
    "          R -= 1\n",
    "        queries[i] = stack[R] - stack[L] - R + L\n",
    "      return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "      stack = []\n",
    "      n = len(s)\n",
    "      for i in range(n):\n",
    "        if s[i] == \"|\": stack.append(i)\n",
    "      if len(stack) < 2:  return [0] * len(queries)\n",
    "\n",
    "      visited = dict()\n",
    "      def check(idx):\n",
    "        if idx in visited:\n",
    "          return visited[idx]\n",
    "        L, R = 0, len(stack) - 1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if idx > stack[mid]:  L = mid + 1\n",
    "          else: R = mid - 1\n",
    "        visited[idx] = L\n",
    "        return L\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        L = check(queries[i][0])\n",
    "        if L == len(stack): \n",
    "          queries[i] = 0\n",
    "          continue\n",
    "        R = check(queries[i][1])\n",
    "        if L == R:\n",
    "          queries[i] = 0\n",
    "          continue\n",
    "        if R == len(stack) or stack[R] > queries[i][1]:\n",
    "          R -= 1\n",
    "        queries[i] = stack[R] - stack[L] - R + L\n",
    "      return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # a[i] 代表从 1 开始，0 ~ 第 i 个中包含的 *\n",
    "        # [i, j] 中 * 的个数为 a[j+1] - a[i]\n",
    "        n = len(s)\n",
    "        a = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            a[i] += a[i-1] + (1 if s[i-1] == '*' else 0)\n",
    "        \n",
    "        # L, R 记录每个 * 最近的左蜡烛和右蜡烛\n",
    "        L = [-1] * n\n",
    "        R = [-1] * n\n",
    "\n",
    "        temp = -1\n",
    "        for i in range(n):\n",
    "            if s[i] == '|':\n",
    "                temp = i\n",
    "            L[i] = temp\n",
    "        \n",
    "        temp = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                temp = i\n",
    "            R[i] = temp\n",
    "\n",
    "        for i, q in enumerate(queries):\n",
    "            if R[q[0]] != -1 and L[q[1]] != -1 and L[q[1]] +1 >= R[q[0]]:\n",
    "                queries[i] = a[L[q[1]]+1] - a[R[q[0]]]\n",
    "            else:\n",
    "                queries[i] = 0\n",
    "        \n",
    "        return queries\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        pos = [i for i in range(n) if s[i] == '|']\n",
    "        ret = []\n",
    "        for l, r in queries:\n",
    "            ri = bisect_right(pos,r) - 1\n",
    "            li = bisect_left(pos, l)\n",
    "            if ri <= li:\n",
    "                ret.append(0)\n",
    "                continue\n",
    "            \n",
    "            lp = pos[li]\n",
    "            lr = pos[ri]\n",
    "                    \n",
    "            # print(pos, l, r, li, ri)\n",
    "            ret.append(lr - lp + 1 - (ri - li + 1))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        candleIndexs = []  # 记录所有蜡烛的索引\n",
    "        for i, c in enumerate(s):\n",
    "            if c != \"*\":\n",
    "                candleIndexs.append(i)\n",
    "        n = len(candleIndexs)\n",
    "\n",
    "        rs = []\n",
    "        for left, right in queries:\n",
    "            left_index = bisect.bisect_left(candleIndexs, left)  # >=left 的蜡烛的位置\n",
    "            right_index = bisect.bisect_right(candleIndexs, right) - 1  # <=right 的蜡烛的位置\n",
    "            # 上面 left_index、right_index 是在 candleIndexs 中的索引\n",
    "            if left_index >= right_index:\n",
    "                rs.append(0)\n",
    "                continue\n",
    "            left = candleIndexs[left_index]\n",
    "            right = candleIndexs[right_index]\n",
    "            # right - left - 1: 两蜡烛之间的字符数, 不包括端点\n",
    "            # right_index - left_index  - 1: 两蜡烛之间的还存在其他蜡烛的数量\n",
    "            rs.append(right - left - right_index + left_index)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        psum = [0] * (n + 1)\n",
    "        for i, ch in enumerate(s):\n",
    "            t = 0 \n",
    "            if ch == \"*\":\n",
    "                t = 1 \n",
    "            psum[i + 1] = psum[i] + t \n",
    "        \n",
    "        last = -1 \n",
    "        left = [-1] * n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"|\":\n",
    "                last = i \n",
    "            left[i] = last\n",
    "        last = -1 \n",
    "        right = [-1] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == \"|\":\n",
    "                last = i \n",
    "            right[i] = last \n",
    "        \n",
    "        ans = []\n",
    "        for li, ri in queries:\n",
    "            lj = right[li]\n",
    "            rj = left[ri]\n",
    "            if lj == -1 or rj == -1 or lj > ri or rj < li:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(psum[rj + 1] - psum[lj])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://github.com/SharingSource/LogicStack-LeetCode/wiki\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, qs: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(qs)\n",
    "        sum_val = [0] * (len(s) + 1)\n",
    "        candle_positions = [i for i, char in enumerate(s) if char == '|']\n",
    "        for i in range(len(s)):\n",
    "            sum_val[i + 1] = sum_val[i] + (s[i] == '*')\n",
    "        if not candle_positions:\n",
    "            return ans\n",
    "        for i in range(len(qs)):\n",
    "            a, b = qs[i]\n",
    "            c, d = -1, -1\n",
    "            # 找到 a 右边最近的蜡烛\n",
    "            l, r = 0, len(candle_positions) - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if candle_positions[mid] >= a:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if candle_positions[r] >= a:\n",
    "                c = candle_positions[r]\n",
    "            else:\n",
    "                continue\n",
    "            # 找到 b 左边最近的蜡烛\n",
    "            l, r = 0, len(candle_positions) - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if candle_positions[mid] <= b:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if candle_positions[r] <= b:\n",
    "                d = candle_positions[r]\n",
    "            else:\n",
    "                continue\n",
    "            if c <= d:\n",
    "                ans[i] = sum_val[d + 1] - sum_val[c]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        cand_idx = [i for i in range(len(s)) if s[i] == '|']\n",
    "        res = []\n",
    "        print(cand_idx)\n",
    "        for left, right in queries:\n",
    "            left_cand_idx = bisect.bisect_left(cand_idx, left) # 0\n",
    "            # right_cand_idx = bisect.bisect_left(cand_idx, right)  #\n",
    "            right_cand_idx = bisect.bisect(cand_idx, right) - 1\n",
    "            if left_cand_idx < right_cand_idx:\n",
    "                res.append((cand_idx[right_cand_idx] - cand_idx[left_cand_idx] + 1) - (right_cand_idx - left_cand_idx + 1))\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "                  #   0 1 2\n",
    "        # cand_idx = [2,5,9]\n",
    "        # 2, 5\n",
    "        # 5-2+1 - (1-0+1) = 4-2=2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n= len(s)\n",
    "        psum = [0]*(n+1)\n",
    "        for i ,ch in enumerate(s):\n",
    "            t = 0\n",
    "            if ch == \"*\":\n",
    "                t = 1\n",
    "            psum[i+1] = psum[i] +t\n",
    "\n",
    "        last = -1\n",
    "        left = [-1]*n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"|\":\n",
    "                last = i \n",
    "            left[i] = last\n",
    "        last = -1 \n",
    "        right = [-1]*n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == \"|\":\n",
    "                last = i \n",
    "            right[i] = last \n",
    "        \n",
    "        ans = []\n",
    "        for li, ri in queries:\n",
    "            lj = right[li]  \n",
    "            rj = left[ri]  \n",
    "            if lj == -1 or rj == -1 or lj > ri or rj < li:  \n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(psum[rj + 1] - psum[lj])\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        m, n = len(s), len(queries)\n",
    "        cnt, ans = [], [0] * n\n",
    "        for i in range(m):\n",
    "            if s[i] == '|':\n",
    "                cnt.append(i)\n",
    "        if not cnt:\n",
    "            return ans\n",
    "        \n",
    "        for i in range(n):\n",
    "            l, r = 0, len(cnt) - 1\n",
    "            x, y = -1, -1\n",
    "            c, d = -1, -1\n",
    "            a, b = queries[i]\n",
    "            # 找右边界，小于等于b的最大的位置\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if cnt[mid] >= a:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "\n",
    "            if cnt[l] >= a:\n",
    "                x = cnt[l]\n",
    "                c = l\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "            l, r = 0, len(cnt) - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if cnt[mid] <= b:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if cnt[l] <= b:\n",
    "                y = cnt[l]\n",
    "                d = l\n",
    "            else:\n",
    "                continue\n",
    "            \n",
    "           \n",
    "            if x <= y:\n",
    "                ans[i] = (y - x - (d - c))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        candles_list = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '|':\n",
    "                candles_list.append(i)\n",
    "        answer = []\n",
    "        for item in queries:\n",
    "            start = item[0]\n",
    "            end = item[1]\n",
    "            start = bisect.bisect_left(candles_list, start)\n",
    "            end = bisect.bisect_right(candles_list, end) - 1\n",
    "            if end <= start:\n",
    "                answer.append(0)\n",
    "            else:\n",
    "                # print(candles_list[end] - candles_list[start] - 1)\n",
    "                # print(end - start - 1)\n",
    "                answer.append(candles_list[end] - candles_list[start] - 1 - (end - start - 1))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # 获取蜡烛的位置\n",
    "        candles = [i  for i in range(len(s)) if s[i]=='|'] \n",
    "        # print(candles)\n",
    "\n",
    "        res = []\n",
    "        for left, right in queries:\n",
    "            candle_left = bisect.bisect_left(candles, left)\n",
    "            candle_right = bisect.bisect_right(candles, right) - 1\n",
    "            # print(candle_right, candle_left)\n",
    "\n",
    "            # 两个蜡烛中间可能还会有蜡烛，蜡烛个数为 candle_right - candle_left\n",
    "            res.append(candles[candle_right] - candles[candle_left] - (candle_right - candle_left) \n",
    "                        if candle_right > candle_left else 0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        candles = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '|':\n",
    "                candles.append(i)\n",
    "        pre_sum = [0] * (len(s) + 1)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                pre_sum[i + 1] = pre_sum[i] + 1\n",
    "            else:\n",
    "                pre_sum[i + 1] = pre_sum[i]\n",
    "        ans = [0] * len(queries)\n",
    "        for i, query in enumerate(queries):\n",
    "            l, r = query[0], query[1]\n",
    "            l = self.find_first_min(l, candles)\n",
    "            r = self.find_last_max(r, candles)\n",
    "            if l >= r or l == -1 or r == len(candles):\n",
    "                continue\n",
    "            l, r = candles[l], candles[r]\n",
    "            ans[i] = pre_sum[r + 1] - pre_sum[l]\n",
    "        return ans\n",
    "\n",
    "    def find_last_max(self, target, candles):\n",
    "        left, right = -1, len(candles) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if candles[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        return left\n",
    "\n",
    "    def find_first_min(self, target, candles):\n",
    "        left, right = 0, len(candles)\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if candles[mid] >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        \n",
    "        lclose, rclose = [-1]*n, [-1]*n\n",
    "        hsum = [0]*(n+1)\n",
    "        la, ne = None, None\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '|':\n",
    "                la = i\n",
    "                hsum[i+1] = hsum[i]\n",
    "            else:\n",
    "                hsum[i+1] = hsum[i]+1\n",
    "            lclose[i] = -1 if la is None else la\n",
    "        for i in reversed(range(n)):\n",
    "            if s[i] == '|':\n",
    "                ne = i\n",
    "            rclose[i] = -1 if ne is None else ne\n",
    "        \n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            l = rclose[l]\n",
    "            r = lclose[r]\n",
    "            if l<0 or r<0 or l>=r:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(hsum[r]-hsum[l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def platesBetweenCandles(self, s: str, queries: list[list[int]]) -> list[int]:\r\n",
    "        #记录盘子的索引\r\n",
    "        import bisect\r\n",
    "        stack = []\r\n",
    "        n = len(s)\r\n",
    "        pre1 = [0] * n\r\n",
    "        ans = []\r\n",
    "        for i in range(len(s)):\r\n",
    "            if s[i] == '|':\r\n",
    "                stack.append(i)\r\n",
    "                pre1[i] = pre1[i - 1]\r\n",
    "            else:\r\n",
    "                pre1[i] = pre1[i - 1] + 1\r\n",
    "        n = len(stack)\r\n",
    "        for i,(x,y) in enumerate(queries):\r\n",
    "            #查找大于等于x的最小值\r\n",
    "            a = bisect.bisect_left(stack, x)\r\n",
    "            #查找小于等于y的最大值\r\n",
    "            b = bisect.bisect_right(stack, y)\r\n",
    "            if a >= (b - 1):\r\n",
    "                ans.append(0)\r\n",
    "            else:\r\n",
    "                ans.append(pre1[stack[b - 1]] - pre1[stack[a]])\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        #记录蜡烛的位置\n",
    "        candle = []\n",
    "        for i, n in enumerate(s):\n",
    "            if n == '|': \n",
    "                candle.append(i)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            pre, post = q[0], q[1]\n",
    "            pre_p  = bisect.bisect_left(candle, pre)\n",
    "            post_p = bisect.bisect_left(candle, post)\n",
    "            #二分查找左闭右开，右边需要判断一下是否相等\n",
    "            if post_p == len(candle) or candle[post_p] > post:\n",
    "                post_p -= 1\n",
    "            if post_p <= pre_p: #只有一根蜡烛或者没蜡烛\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            ans.append(candle[post_p] - candle[pre_p] - (post_p - pre_p))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        # 0-i的盘子个数\n",
    "        cnt = [0]*n\n",
    "        # 距离i左边最近的蜡烛的下标，不存在则为-1\n",
    "        left = [-1]*n\n",
    "        l = -1\n",
    "        res = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c == '|':\n",
    "                l = i\n",
    "            else:\n",
    "                res += 1\n",
    "            left[i] = l\n",
    "            cnt[i] = res\n",
    "        # 距离i右边最近的蜡烛的下标，不存在则为-1\n",
    "        right = [-1]*n\n",
    "        r = -1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "        ans = [0]*len(queries)\n",
    "        # 开始查询\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            x = right[x]\n",
    "            y = left[y]\n",
    "            if x >= 0 and y >=0 and y > x:\n",
    "                ans[i] = cnt[y]-cnt[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        plates = [0] * n\n",
    "        left_candle = [0] * n\n",
    "        right_candle = [0] * n\n",
    "        pre_p = 0\n",
    "        pre_c = -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                pre_p += 1\n",
    "            else:\n",
    "                pre_c = i\n",
    "            plates[i] = pre_p\n",
    "            left_candle[i] = pre_c\n",
    "        pre_c = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                pre_c = i\n",
    "            right_candle[i] = pre_c\n",
    "\n",
    "        \n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            left, right = right_candle[left], left_candle[right]\n",
    "            if left >= 0 and right >= 0 and right > left:\n",
    "                ans.append(plates[right] - plates[left])\n",
    "            else:\n",
    "                ans.append(0)\n",
    "\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        candles = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '|':\n",
    "                candles.append(i)\n",
    "        pre_sum = [0] * (len(s) + 1)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                pre_sum[i + 1] = pre_sum[i] + 1\n",
    "            else:\n",
    "                pre_sum[i + 1] = pre_sum[i]\n",
    "        ans = [0] * len(queries)\n",
    "        for i, query in enumerate(queries):\n",
    "            l, r = query[0], query[1]\n",
    "            l = self.find_first_min(l, candles)\n",
    "            r = self.find_last_max(r, candles)\n",
    "            if l >= r or l == -1 or r == len(candles):\n",
    "                continue\n",
    "            l, r = candles[l], candles[r]\n",
    "            ans[i] = pre_sum[r + 1] - pre_sum[l]\n",
    "        return ans\n",
    "\n",
    "    def find_last_max(self, target, candles):\n",
    "        left, right = -1, len(candles) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if candles[mid] > target:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        return left\n",
    "\n",
    "    def find_first_min(self, target, candles):\n",
    "        left, right = 0, len(candles)\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if candles[mid] >= target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        # presum: 统计*的前缀和, lefts: 统计每个坐标左边最近的|的坐标, rights: 统计每个坐标右边最近的|的坐标\n",
    "        presum, lefts, rights, l = [0] * (n + 1), [-1] * n, [-1] * n, -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '*':\n",
    "                # 当前字符为*，前缀和个数加一\n",
    "                presum[i + 1] = presum[i] + 1\n",
    "            else:\n",
    "                # 当前字符为|，前缀和个数不变\n",
    "                presum[i + 1] = presum[i]\n",
    "                # 更新最新的坐标最近坐标（接下来下次更新前最近的都是i）\n",
    "                l = i\n",
    "            lefts[i] = l\n",
    "        # 右边与左边的更新同理，只需要从右往左\n",
    "        r = -1\n",
    "        for i, c in enumerate(s[::-1]):\n",
    "            if c == '|':\n",
    "                r = n - 1 - i\n",
    "            rights[n - 1 - i] = r\n",
    "        # 最终答案只有 左查询点的右边有蜡烛、右查询点的左边有蜡烛、且右边的蜡烛在左边的蜡烛右边中间才可能有*，否则肯定是0个\n",
    "        return [presum[lefts[r]] - presum[rights[l]] if rights[l] >= 0 and lefts[r] >= 0 and rights[l] < lefts[r] else 0 for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        # presum: 统计*的前缀和, lefts: 统计每个坐标左边最近的|的坐标, rights: 统计每个坐标右边最近的|的坐标\n",
    "        presum, lefts, rights, l = [0] * (n + 1), [-1] * n, [-1] * n, -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '*':\n",
    "                # 当前字符为*，前缀和个数加一\n",
    "                presum[i + 1] = presum[i] + 1\n",
    "            else:\n",
    "                # 当前字符为|，前缀和个数不变\n",
    "                presum[i + 1] = presum[i]\n",
    "                # 更新最新的坐标最近坐标（接下来下次更新前最近的都是i）\n",
    "                l = i\n",
    "            lefts[i] = l\n",
    "        # 右边与左边的更新同理，只需要从右往左\n",
    "        r = -1\n",
    "        for i, c in enumerate(s[::-1]):\n",
    "            if c == '|':\n",
    "                r = n - 1 - i\n",
    "            rights[n - 1 - i] = r\n",
    "        # 最终答案只有 左查询点的右边有蜡烛、右查询点的左边有蜡烛、且右边的蜡烛在左边的蜡烛右边中间才可能有*，否则肯定是0个\n",
    "        return [presum[lefts[r]] - presum[rights[l]] if rights[l] >= 0 and lefts[r] >= 0 and rights[l] < lefts[r] else 0 for l, r in queries]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # Benhao总的前缀和 + 辅助数组判断做法\n",
    "        # 辅助数组用于记录最近的蜡烛的下标\n",
    "        n = len(s)\n",
    "        # pre: 统计*的前缀和, lefts: 统计每个坐标左边最近的|的坐标, rights: 统计每个坐标右边最近的|的坐标\n",
    "        pre, lefts, rights = [0] * (n + 1), [-1] * n, [-1] * n\n",
    "        l, r = -1, -1\n",
    "        for i, c in enumerate(s):\n",
    "            # 盘子\n",
    "            if c == '*':\n",
    "                pre[i + 1] = pre[i] + 1\n",
    "            # 蜡烛\n",
    "            else:\n",
    "                pre[i + 1] = pre[i]\n",
    "                l = i\n",
    "            lefts[i] = l\n",
    "        for i, c in enumerate(s[::-1]):\n",
    "            if c == '|':\n",
    "                r = n - 1 - i\n",
    "            rights[n - 1 - i] = r\n",
    "        \n",
    "        res = [0] * len(queries)\n",
    "        # 最终答案只有 左查询点的右边有蜡烛、右查询点的左边有蜡烛、且右边的蜡烛在左边的蜡烛右边中间才可能有*，否则肯定是0个\n",
    "        for i, (l, r) in enumerate(queries):\n",
    "            if lefts[r] >= 0 and rights[l] >= 0 and rights[l] < lefts[r]:\n",
    "                res[i] = pre[lefts[r]] - pre[rights[l]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        left, right = [-1]*n, [-1]*n\n",
    "        prev = -1\n",
    "        for i in range(n):\n",
    "            if s[i] == '|':\n",
    "                prev = i\n",
    "            left[i] = prev\n",
    "        prev = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                prev = i\n",
    "            right[i] = prev\n",
    "        acc = [0]*n\n",
    "        ct = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == '|':\n",
    "                ct += 1\n",
    "            acc[i] = ct\n",
    "        ans = []\n",
    "        for x, y in queries:\n",
    "            right_id, left_id = right[x], left[y]\n",
    "            if right_id == -1 or left_id == -1 or right_id >= left_id:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                n_bar = acc[left_id-1]-acc[right_id]\n",
    "                ans.append(left_id - right_id - 1 - n_bar)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "\n",
    "        total = 0\n",
    "        pre_sum = [0] * n\n",
    "        sum = 0\n",
    "\n",
    "        left = [0] * n\n",
    "        l = -1\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == \"*\":\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            pre_sum[i] = sum\n",
    "            left[i] = l\n",
    "        \n",
    "        right = [0] * n\n",
    "        r = - 1\n",
    "        for i in range (n-1, -1, -1):\n",
    "            if s[i] != \"*\":\n",
    "                r = i\n",
    "            right[i] = r\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (q1, q2) in enumerate(queries):\n",
    "            x = right[q1]\n",
    "            y = left[q2]\n",
    "\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = pre_sum[y] - pre_sum[x]\n",
    "                \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # 相似题目： 接雨水，找出每个位置左右两侧满足条件的最近索引\n",
    "        n = len(s)\n",
    "        # 前缀和\n",
    "        preSum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            cur = 0 if s[i] == \"|\" else 1\n",
    "            preSum[i + 1] = preSum[i] + cur\n",
    "\n",
    "        # FIXME 使用-1 作为默认值，标识找不到目标|的情况\n",
    "        # 找出每个*，右侧最近|符号索引\n",
    "        right_sign = [-1] * n\n",
    "        R1 = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == \"*\":\n",
    "                right_sign[i] = R1\n",
    "            else:\n",
    "                # | => 取自身索引\n",
    "                right_sign[i] = i\n",
    "                R1 = i\n",
    "\n",
    "        left_sign = [-1] * n\n",
    "        L1 = - 1\n",
    "        for i in range(n):\n",
    "            if s[i] == \"*\":\n",
    "                left_sign[i] = L1\n",
    "            else:\n",
    "                # | => 取自身索引\n",
    "                left_sign[i] = i\n",
    "                L1 = i\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, info in enumerate(queries):\n",
    "            x, y = info\n",
    "            x = right_sign[x]\n",
    "            y = left_sign[y]\n",
    "            # 排除-1不合理情况\n",
    "            if 0 <= x < y and y >= 0:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        presum = [0] * (n + 1)\n",
    "        ss = 0\n",
    "        ls = list()\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"*\":\n",
    "                ss += 1\n",
    "            else:\n",
    "                ls.append(i)\n",
    "            presum[i + 1] = ss\n",
    "        \n",
    "        def getbe(x, ls):\n",
    "            # 考虑边界\n",
    "            if not ls or x > ls[-1]:\n",
    "                return -1\n",
    "            l, r = 0, len(ls) - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if ls[mid] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return ls[l]\n",
    "        \n",
    "        def getse(x, ls):\n",
    "            if not ls or x < ls[0]:\n",
    "                return -1\n",
    "            l, r = 0, len(ls) - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if ls[mid] <= x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return ls[l]\n",
    "        \n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = getbe(x, ls), getse(y, ls)\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = presum[y + 1] - presum[x]\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "\n",
    "        left = []\n",
    "        for index in range(n):\n",
    "            if s[index] == '|':\n",
    "                left.append(index)\n",
    "            elif index == 0:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(left[-1])\n",
    "        \n",
    "        right = []\n",
    "        for index in range(n - 1, -1, -1):\n",
    "            if s[index] == '|':\n",
    "                right.append(index)\n",
    "            elif index == n - 1:\n",
    "                right.append(-1)\n",
    "            else:\n",
    "                right.append(right[-1])\n",
    "        right.reverse()\n",
    "\n",
    "        if s[0] == '|':\n",
    "            cnt = [1]\n",
    "        else:\n",
    "            cnt = [0]\n",
    "        \n",
    "        for char in s[1:]:\n",
    "            cnt.append(cnt[-1])\n",
    "            if char == '|':\n",
    "                cnt[-1] += 1\n",
    "        \n",
    "        res = []\n",
    "        for x, y in queries:\n",
    "            now = cnt[y]\n",
    "            if x > 0:\n",
    "                now -= cnt[x - 1]\n",
    "            \n",
    "            if now < 2:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(left[y] - right[x] + 1 - now)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # \"*\"的数量的前缀和\n",
    "        pre = [0]\n",
    "        for c in s:\n",
    "            pre.append(pre[-1] + int(c == '*'))\n",
    "        n = len(s)\n",
    "        # 当前坐标自己以及左边的第一个\"|\"位置\n",
    "        left = [-1] * n\n",
    "        if s[0] == '|':\n",
    "            left[0] = 0\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i - 1] if s[i] != '|' else i\n",
    "        # 当前坐标自己以及右边的第一个\"|\"位置\n",
    "        right = [-1] * n\n",
    "        if s[n - 1] == '|':\n",
    "            right[n - 1] = n - 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = right[i + 1] if s[i] != '|' else i\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            l, r = right[a], left[b]\n",
    "            # print(a, b, l, r)\n",
    "            if l == -1 or r == -1 or l >= r:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(pre[r + 1] - pre[l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        cand_idx = [i for i in range(len(s)) if s[i] == '|']\n",
    "        res = []\n",
    "        # print(cand_idx)\n",
    "        for left, right in queries:\n",
    "            left_cand_idx = bisect.bisect_left(cand_idx, left) # 0\n",
    "            right_cand_idx = bisect.bisect_right(cand_idx, right) - 1  #\n",
    "            # print(left_cand_idx, ',', right_cand_idx)\n",
    "            # right_cand_idx = bisect.bisect(cand_idx, right) - 1\n",
    "            if left_cand_idx < right_cand_idx:\n",
    "                res.append((cand_idx[right_cand_idx] - cand_idx[left_cand_idx] + 1) - (right_cand_idx - left_cand_idx + 1))\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res\n",
    "\n",
    "\n",
    "                  #   0 1 2\n",
    "        # cand_idx = [2,5,9]\n",
    "        # 2, 5\n",
    "        # 5-2+1 - (1-0+1) = 4-2=2\n",
    "#   0  1   2   3  4   5\n",
    "#  [3, 6, 12, 15, 16, 19]\n",
    "#   3             16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        a = [0] * (len(s) + 1)\n",
    "        cur = x = 0\n",
    "        p = []\n",
    "        for i, c in enumerate(s):\n",
    "            a[i + 1] = a[i]\n",
    "            if c == '*':\n",
    "                a[i + 1] += 1\n",
    "            else:\n",
    "                p.append(i)\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (left, right) in enumerate(queries):\n",
    "            l = bisect_left(p, left)\n",
    "            r = bisect_right(p, right) - 1\n",
    "            if l >= r:\n",
    "                continue\n",
    "            ans[i] = a[p[r]] - a[p[l]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        nums = [int(c=='*') for c in s]\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        loc = [i for i, c in enumerate(s) if c == '|']\n",
    "        if len(loc) == 0:\n",
    "            return [0] * len(queries)\n",
    "        \n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            i = bisect_left(loc, left)\n",
    "            j = bisect_right(loc, right)\n",
    "            l = loc[i] if i < len(loc) else loc[i-1]\n",
    "            r = loc[j-1] if j-1 >= 0 else loc[j]\n",
    "            if l >= r:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(pre[r+1]-pre[l])\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        presum = [0]\n",
    "        left = []\n",
    "        right = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                presum.append(presum[-1] + 1)\n",
    "                if not left:\n",
    "                    left.append(-1)\n",
    "                else:\n",
    "                    left.append(left[-1])\n",
    "            else:\n",
    "                presum.append(presum[-1])\n",
    "                left.append(i)\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == '*':\n",
    "                if not right:\n",
    "                    right.append(-1)\n",
    "                else:\n",
    "                    right.append(right[-1])\n",
    "            else:\n",
    "                right.append(i)\n",
    "        right = right[::-1]\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            if left[b] != -1 and right[a] != -1 and left[b] > right[a]:\n",
    "                ans.append(presum[left[b] + 1] - presum[right[a] + 1])\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        前缀和 + 二分\n",
    "    '''\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        pre = [0] * (n + 1)\n",
    "        ls = []\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i]\n",
    "            if s[i] == '|':\n",
    "                ls.append(i)\n",
    "            else:\n",
    "                pre[i + 1] += 1\n",
    "        ans = [0] * len(queries)\n",
    "        if len(ls) == 0: return ans\n",
    "        for i, (L, R) in enumerate(queries):\n",
    "            if L == R: continue\n",
    "            # 二分找最近的蜡烛 L往右找 R往左找\n",
    "            idx1 = self.rightBound(ls, L)\n",
    "            idx2 = self.leftBound(ls, R)\n",
    "            if idx1 != -1 and idx2 != -1 and idx1 < idx2:\n",
    "                ans[i] = pre[idx2 + 1] - pre[idx1]\n",
    "        return ans\n",
    "\n",
    "    # 二分找右边界\n",
    "    def rightBound(self, a: List[int], t: int) -> int:\n",
    "        l, r = 0, len(a) - 1\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if a[mid] < t:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid \n",
    "        return a[l] if a[l] >= t else -1\n",
    "    \n",
    "    # 二分找左边界\n",
    "    def leftBound(self, a: List[int], t: int) -> int:\n",
    "        l, r = 0, len(a) - 1\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if a[mid] > t:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return a[l] if a[l] <= t else -1\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        ss = [0]*(n + 1)\n",
    "        left = [0]*(n + 1)\n",
    "        right = [0]*(n + 1)\n",
    "        pre = -1\n",
    "        for i,x in enumerate(s,1):\n",
    "            if x == '*':\n",
    "                ss[i] = ss[i - 1] + 1\n",
    "                left[i-1] = pre\n",
    "            else:\n",
    "                ss[i] = ss[i - 1]\n",
    "                pre = i\n",
    "                left[i-1] = pre\n",
    "        pre = n-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == '*':\n",
    "                right[i] = pre\n",
    "            else:\n",
    "                pre = i\n",
    "                right[i] = pre\n",
    "        \n",
    "        ans = []\n",
    "        for l,r in queries:\n",
    "            a,b = right[l],left[r]\n",
    "            if a< b:\n",
    "                ans.append(ss[b] - ss[a])\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        presum = [0] * (n + 1)\n",
    "\n",
    "        ls = []\n",
    "        ss = 0\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"*\":\n",
    "                ss += 1\n",
    "            else:\n",
    "                ls.append(i)\n",
    "            presum[i + 1] = ss\n",
    "\n",
    "        def getbe(x, ls):\n",
    "            l, r = 0, len(ls)-1\n",
    "            if not ls or ls[-1] < x:\n",
    "                return -1\n",
    "            # 保证在区间内\n",
    "            while l < r:\n",
    "                mid = l + r >>1\n",
    "                if ls[mid] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return ls[l]\n",
    "\n",
    "        def getse(x, ls):\n",
    "            l, r = 0, len(ls) - 1\n",
    "            if not ls or ls[0] > x:\n",
    "                return -1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if ls[mid] <= x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return ls[l]\n",
    "\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = getbe(x, ls), getse(y, ls)\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = presum[y+1] - presum[x]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        def find_left_most(target):\n",
    "            l, r = -1, len(plates)\n",
    "            while l + 1 < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if plates[mid] < target:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            return r\n",
    "        \n",
    "        def find_right_most(target):\n",
    "            l, r = -1, len(plates)\n",
    "            while l + 1 < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if plates[mid] <= target:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l\n",
    "        plates = []\n",
    "        acc_cnt = defaultdict(int)\n",
    "        cnt = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"*\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                acc_cnt[i] = cnt\n",
    "                plates.append(i)\n",
    "        res = []\n",
    "        print(acc_cnt)\n",
    "        for left_bnd, right_bnd in queries:\n",
    "            most_left = find_left_most(left_bnd)\n",
    "            most_right = find_right_most(right_bnd)\n",
    "            print(most_left, most_right)\n",
    "            if most_left >= most_right:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                ans = acc_cnt[plates[most_right]] - acc_cnt[plates[most_left]]\n",
    "                res.append(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/plates-between-candles/solutions/1317015/zha-zhu-zhi-jian-de-pan-zi-by-leetcode-s-ejst/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # 如何求pre[i]\n",
    "        n = len(s)\n",
    "        pre = [0]*n\n",
    "        cnt = 0\n",
    "        left,l = [0]*n,-1\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                cnt += 1\n",
    "            else:\n",
    "                l = i\n",
    "            pre[i] = cnt\n",
    "            left[i] = l\n",
    "        right,r = [0]*n,-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        # pre[i]表示从0-i有pre[i]只盘子在蜡烛中间\n",
    "        ans = [0]*len(queries)\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            x,y = right[x],left[y]\n",
    "            if x >= 0 and y >= 0 and x < y: \n",
    "                ans[i] = pre[y]-pre[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        #前缀和\n",
    "        n = len(s)\n",
    "        lcandle = [0 for i in range(n)]\n",
    "        rcandle = [0 for i in range(n)]\n",
    "        plate = [0 for i in range(n)]\n",
    "        if s[0] == '|':\n",
    "            lcandle[0] = 0\n",
    "\n",
    "        if s[n - 1] == '|':\n",
    "            rcandle[n - 1] = n - 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            lcandle[i] = i if s[i] == '|' else lcandle[i - 1]\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            rcandle[i] = i if s[i] == '|' else rcandle[i + 1]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            plate[i] = plate[i - 1] + 1 if s[i - 1] == '*' else plate[i - 1]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for q in queries:\n",
    "            left, right = q[0], q[1]\n",
    "            l = rcandle[left]\n",
    "            r = lcandle[right]\n",
    "            if l >= right - 1 or r <= left + 1:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(plate[r] - plate[l])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        left, l = [0]*n, -1\n",
    "        preSum, sum = [0]*n, 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "        \n",
    "        right, r = [0]*n, -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "        \n",
    "        ans = [0]*len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        A=[]\n",
    "        for i,v in enumerate(s):\n",
    "            if v==\"|\":\n",
    "                A.append(i)\n",
    "        ans=[]\n",
    "        print(A)\n",
    "        for a,b in queries:\n",
    "            idx=bisect_left(A,a)\n",
    "            if idx<len(A):\n",
    "                x=A[idx]\n",
    "            else:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            idy=bisect_right(A,b)\n",
    "            if idy==0:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            y=A[idy-1]\n",
    "            if y<=x:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            cur=y-x-1-(idy-idx-2)\n",
    "            if cur>0:\n",
    "                ans.append(cur)\n",
    "            else:\n",
    "                ans.append(0)\n",
    "            print(idx,idy,x,y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        lefts = [0] * n   \n",
    "        left = -1\n",
    "        cnts = [0] * n\n",
    "        cnt = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == \"|\":\n",
    "                left = i\n",
    "            else:\n",
    "                cnt += 1\n",
    "            lefts[i] = left\n",
    "            cnts[i] = cnt \n",
    "\n",
    "        rights = [0] * n\n",
    "        right = -1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == \"|\":\n",
    "                right = i\n",
    "            rights[i] = right\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (l, r) in enumerate(queries):\n",
    "            l,r = rights[l], lefts[r]\n",
    "            if l >= 0 and r >= 0 and l < r:\n",
    "                ans[i] = cnts[r] - cnts[l]\n",
    "\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        pre = -1\n",
    "        left = [-1 for _ in s]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"|\":\n",
    "                pre = i \n",
    "            left[i] = pre\n",
    "        pre = len(s)\n",
    "        right = [pre for _ in s]\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            if s[i] == \"|\":\n",
    "                pre = i \n",
    "            right[i] = pre\n",
    "\n",
    "        s = [0 if i == \"|\" else 1 for i in s]\n",
    "        pre = [0]\n",
    "        for i in s:\n",
    "            pre.append(pre[-1]+i)\n",
    "        res = [0 for _ in queries]\n",
    "        for i in range(len(queries)):\n",
    "            l, r = queries[i]\n",
    "            first, last = right[l], left[r]\n",
    "            if first > r or last < l:\n",
    "                continue\n",
    "            res[i] = pre[last+1]-pre[first]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/plates-between-candles/solution/zha-zhu-zhi-jian-de-pan-zi-by-leetcode-s-ejst/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        candles, plates = list(), list()\n",
    "\n",
    "        cur = 0\n",
    "\n",
    "        for i, x in enumerate(s):\n",
    "\n",
    "            if x == '|':\n",
    "\n",
    "                candles.append(i)\n",
    "\n",
    "            else:\n",
    "\n",
    "                cur += 1\n",
    "\n",
    "            plates.append(cur)\n",
    "\n",
    "\n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        for i, j in queries:\n",
    "\n",
    "            i_, j_ = bisect.bisect_left(candles, i), bisect.bisect_left(candles, j)\n",
    "\n",
    "            if j_ == len(candles) or candles[j_] > j:\n",
    "\n",
    "                j_ -= 1\n",
    "\n",
    "            if i_ >= j_:\n",
    "\n",
    "                ans.append(0)\n",
    "\n",
    "            else:\n",
    "\n",
    "                ans.append(plates[candles[j_]]-plates[candles[i_]])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        l = len(s)\n",
    "        pref = [0]*l\n",
    "        lc = [-1]*l\n",
    "        rc = [-1]*l\n",
    "        lc[0] = 0 if s[0] == '|' else -1\n",
    "        pref[0] = 0 if s[0] == '|' else 1\n",
    "        rc[l-1] = l-1 if s[l-1] == '|' else -1\n",
    "        for i in range(1,l):\n",
    "            if s[i] == '*':\n",
    "                pref[i] = pref[i-1]+1\n",
    "            else:\n",
    "                pref[i] = pref[i-1]\n",
    "        for i in range(1,l):\n",
    "            lc[i] = i if s[i] =='|' else lc[i-1]\n",
    "        for i in range(l-2,-1,-1):\n",
    "            rc[i] = i if s[i] =='|' else rc[i+1]\n",
    "        res = []\n",
    "        print(rc)\n",
    "        print(lc)\n",
    "        print(pref)\n",
    "        for q in queries:\n",
    "            \n",
    "            \n",
    "            li = rc[q[0]]\n",
    "            ri = lc[q[1]]\n",
    "            if li >= q[1]-1 or ri<=q[0]+1:\n",
    "                res.append(0)\n",
    "                continue\n",
    "            else:\n",
    "                res.append(pref[ri]-pref[li])\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        # 找到给定区间内最左侧和最右侧的两个蜡烛，这样两个蜡烛之间的所有盘子都是符合条件的。\n",
    "        n = len(s)\n",
    "        pre = [0]*n\n",
    "        cnt = 0\n",
    "        # 找最左侧\n",
    "        # left[i]表示i左边的第一根蜡烛\n",
    "        left,l = [0]*n,-1\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch == '|':\n",
    "                l = i\n",
    "            else:\n",
    "                cnt += 1\n",
    "            pre[i] = cnt\n",
    "            left[i] = l\n",
    "        # 找最右侧\n",
    "        right,r = [0]*n,-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        # pre[i]表示从0-i有pre[i]只盘子\n",
    "        ans = [0]*len(queries)\n",
    "        for i,(x,y) in enumerate(queries):\n",
    "            x,y = right[x],left[y]\n",
    "            if x >= 0 and y >= 0 and x < y: \n",
    "                ans[i] = pre[y]-pre[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum_ = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum_ += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum_\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        p = [0] * (n + 1)\n",
    "        l = [0] * n\n",
    "        r = [0] * n\n",
    "        j = n - 1\n",
    "        p1 = -1\n",
    "        q1 = -1\n",
    "        for i in range(n):\n",
    "            p[i + 1] = p[i] + (s[i] == '*')\n",
    "            if s[i] == '|':\n",
    "                p1 = i\n",
    "            if s[j] == '|':\n",
    "                q1 = j \n",
    "            l[i] = p1\n",
    "            r[j] = q1 \n",
    "            j -= 1\n",
    "       \n",
    "        ans = [0] * len(queries)\n",
    "        for idx,q in enumerate(queries):\n",
    "            left,right = q[0],q[1]\n",
    "            c = r[left]\n",
    "            d = l[right]\n",
    "            if c != - 1 and c <= d:\n",
    "                ans[idx] = p[d + 1] - p[c]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        prefix = [0]*(len(s)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1]\n",
    "            if s[i-1] == '*':\n",
    "                prefix[i] += 1\n",
    "        stack = [] \n",
    "        hashmap = [0]*len(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '*':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack:\n",
    "                    hashmap[stack.pop()] = i \n",
    "                hashmap[i] = i \n",
    "        \n",
    "        stack = []\n",
    "        hashmap2 = [0]*len(s)\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i] == '*':\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack:\n",
    "                    hashmap2[stack.pop()] = i\n",
    "                hashmap2[i] = i \n",
    "\n",
    "        # print(prefix)\n",
    "        # print(hashmap)\n",
    "        # print(hashmap2)\n",
    "\n",
    "        def check(left,right):\n",
    "            RI = hashmap[left]\n",
    "            LI = hashmap2[right]\n",
    "            if LI < left or RI > right:\n",
    "                return 0 \n",
    "            return prefix[LI] - prefix[RI]\n",
    "        res = []\n",
    "        for i,j in queries:\n",
    "            res.append(check(i,j))\n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        preSum, sum = [0] * n, 0\n",
    "        left, l = [0] * n, -1\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                sum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            preSum[i] = sum\n",
    "            left[i] = l\n",
    "        right, r = [0] * n, -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                r = i\n",
    "            right[i] = r\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                ans[i] = preSum[y] - preSum[x]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        less running time\n",
    "        1. for every index of s: O(N)\n",
    "            (1)count * before this index; \n",
    "            (2)the most right '|' index near it; \n",
    "            (3)the most left '|' index near it\n",
    "        2. for every query:O(M)\n",
    "            get the most right '|' index of query[0]--li\n",
    "            get the most left '|' index of query[1]--ri\n",
    "        3. numbers of '*' is the numebers of '*' between li and ri\n",
    "        O(m + n)\n",
    "        '''\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        #count * before every index\n",
    "        pNumbers = [0]\n",
    "        for i in range(1, n):\n",
    "            if s[i-1] == '*':\n",
    "                pNumbers.append(pNumbers[i-1] + 1)\n",
    "            else:\n",
    "                pNumbers.append(pNumbers[i-1])\n",
    "\n",
    "        #most right index of '|'\n",
    "        lIndex = [-2] * n\n",
    "        if s[-1] == '|':\n",
    "            lIndex[-1] = n - 1\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                lIndex[i] = i\n",
    "            else:\n",
    "                lIndex[i] = lIndex[i + 1]\n",
    "        \n",
    "        #most left index of '|'\n",
    "        rIndex = [-2] * n\n",
    "        if s[0] == '|':\n",
    "            rIndex[0] = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if s[i] == '|':\n",
    "                rIndex[i] = i\n",
    "            else:\n",
    "                rIndex[i] = rIndex[i - 1]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        #iterate queries\n",
    "        for l, r in queries:\n",
    "            li = lIndex[l]\n",
    "            ri = rIndex[r]\n",
    "            if li == -2 or ri == -2:\n",
    "                res.append(0)\n",
    "            elif li >= ri:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(pNumbers[ri] - pNumbers[li])\n",
    "         \n",
    "        print(pNumbers, lIndex, rIndex)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "        '''\n",
    "        brute force\n",
    "\n",
    "        #for every query, count the number of * that satisfy the rule\n",
    "        #T(n) = m * n (m is the length of queries, n is the length of s)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for q in queries:\n",
    "            l = q[0]\n",
    "            r = q[1]\n",
    "            count = 0\n",
    "\n",
    "            # the numbers of * that satisfy the rule is * between the first | and the last | \n",
    "            while s[l] != '|' and l < r:\n",
    "                l += 1\n",
    "\n",
    "            while s[r] != '|' and r > l:\n",
    "                r -= 1\n",
    "            \n",
    "            print(s[l:r+1])\n",
    "\n",
    "            for i in range(l, r): \n",
    "                if s[i] == '*':\n",
    "                    count += 1\n",
    "            res.append(count)\n",
    "        \n",
    "        return res\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        prefix_sum = [0] * n\n",
    "        cumsum = 0\n",
    "\n",
    "        left = [0] * n\n",
    "\n",
    "        l = -1\n",
    "\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == \"*\":\n",
    "                cumsum += 1\n",
    "            else:\n",
    "                l = i\n",
    "            prefix_sum[i] = cumsum\n",
    "            left[i] = l\n",
    "\n",
    "        right, r = [0]*n, -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == \"|\":\n",
    "                r = i\n",
    "            right[i] = r\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            x, y = right[x], left[y]\n",
    "            if x >= 0 and y >= 0 and x < y:\n",
    "                res[i] = prefix_sum[y] - prefix_sum[x]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        cntp = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '*':\n",
    "                cnt += 1\n",
    "            cntp.append(cnt)\n",
    "        lc = []\n",
    "        lci = -1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '|':\n",
    "                lci=i\n",
    "            lc.append(lci)\n",
    "\n",
    "        rc = []\n",
    "        rci = -1\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                rci=i\n",
    "            rc.append(rci)\n",
    "        rc.reverse()\n",
    "        ret = []\n",
    "        for q in queries:\n",
    "            l, r = rc[q[0]], lc[q[1]]\n",
    "            if l == -1 or r == -1 or l>r:\n",
    "                ret.append(0)\n",
    "            else:\n",
    "                ret.append(cntp[r]-cntp[l])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        cntp = []\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c == '*':\n",
    "                cnt += 1\n",
    "            cntp.append(cnt)\n",
    "        lc = []\n",
    "        lci = -1\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '|':\n",
    "                lci=i\n",
    "            lc.append(lci)\n",
    "\n",
    "        rc = []\n",
    "        rci = -1\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                rci=i\n",
    "            rc.append(rci)\n",
    "        rc.reverse()\n",
    "        ret = []\n",
    "        for q in queries:\n",
    "            l, r = rc[q[0]], lc[q[1]]\n",
    "            if l == -1 or r == -1 or l>r:\n",
    "                ret.append(0)\n",
    "            else:\n",
    "                ret.append(cntp[r]-cntp[l])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        plates = [0] * n\n",
    "        candles = [0] * n\n",
    "        pre_p = pre_c = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                pre_p += 1\n",
    "            else:\n",
    "                pre_c += 1\n",
    "            plates[i] = pre_p\n",
    "            candles[i] = pre_c\n",
    "        \n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            if candles[left] == candles[right]:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                if s[left] != '|':\n",
    "                    left = bisect_left(candles, candles[left]+1, lo=left, hi=right+1)\n",
    "                if s[right] != '|':\n",
    "                    right = bisect_left(candles, candles[right], lo=left, hi=right+1)\n",
    "                ans.append(plates[right]-plates[left])\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        leftCandles = [-1] * n\n",
    "        rightCandles = [n] * n\n",
    "        preSum = [0] * (n+1)\n",
    "        #记录当前位置左侧最近的蜡烛位置\n",
    "        candle = -1\n",
    "        for i in range(n):\n",
    "            if s[i] == '|':\n",
    "                candle = i\n",
    "            leftCandles[i] = candle\n",
    "\n",
    "        #记录当前位置右侧最近的蜡烛位置\n",
    "        candle = n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                candle = i\n",
    "            rightCandles[i] = candle\n",
    "        \n",
    "        #计算盘子前缀和\n",
    "        for i in range(1, n+1):\n",
    "            preSum[i] = preSum[i-1] + (1 if s[i-1] == '*' else 0)\n",
    "\n",
    "        answer = []\n",
    "        for query in queries:\n",
    "            left_candle_index = rightCandles[query[0]]\n",
    "            right_candle_index = leftCandles[query[1]]\n",
    "            \n",
    "            if left_candle_index == n or right_candle_index == -1 or left_candle_index >= right_candle_index:\n",
    "                answer.append(0)\n",
    "            else:\n",
    "                answer.append(preSum[right_candle_index] - preSum[left_candle_index])\n",
    "        \n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        left, right = [n for _ in range(n)], [-1 for _ in range(n)]\n",
    "        prv = n\n",
    "        for i, x in enumerate(s):\n",
    "            if x == '|':\n",
    "                prv = i\n",
    "            left[i] = prv\n",
    "        prv = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == '|':\n",
    "                prv = i\n",
    "            right[i] = prv\n",
    "\n",
    "        presum = [0 for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i] + (1 if s[i] == '|' else 0)\n",
    "        #print(list(zip(range(len(presum)), presum)))\n",
    "        \n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            print(l, r, right[l], left[r])\n",
    "            if right[l] >= left[r] or right[l] == -1 or left[r] == n:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(left[r] - right[l] + 1 - presum[left[r]+1] + presum[right[l]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
    "        n = len(s)\n",
    "        pre = list(accumulate([int(w==\"*\") for w in s], initial=0))\n",
    "        \n",
    "        left = [-1]*n\n",
    "        ind = -1\n",
    "        for i in range(n):\n",
    "            if s[i] == \"|\":\n",
    "                ind = i\n",
    "            left[i] = ind\n",
    "            \n",
    "        right = [-1]*n\n",
    "        ind = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == \"|\":\n",
    "                ind = i\n",
    "            right[i] = ind\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            x = right[a]\n",
    "            y = left[b]\n",
    "            if -1<x<=y:\n",
    "                ans.append(pre[y+1]-pre[x])\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
